package main

import "fmt"

//插入排序,详见insertSort.png

// 插入排序是一种简单直观的排序算法，其工作原理类似于人们整理扑克牌时的操作。具体步骤如下： 时间复杂度为 O(n^2)，其中 (n) 是数组的长度
// 从第二个元素开始：
// 假设第一个元素已经排序。
// 逐个将后面的元素插入到前面已排序部分的正确位置：
// 取出当前元素，与已排序部分的元素从后向前比较。
// 如果当前元素小于已排序部分的元素，则将已排序部分的元素向后移动一位。
// 重复上述步骤，直到找到当前元素的正确位置，将其插入。
// 重复上述过程：
// 依次对每个元素进行上述操作，直到整个数组有序。
func main() {
	var arr [5]int = [5]int{23, 0, 12, 56, 34}
	insertSortMinToMax(&arr)
	fmt.Println(arr)
}

// insertSortMinToMax
//
//	@Description: 插入排序   O(n^2)
//	@param arr
func insertSortMinToMax(arr *[5]int) {

	for i := 1; i < len(*arr); i++ {
		//第一次，给第二个元素找位置，第二次，给第三个元素找位置，依次类推
		insertValue := (*arr)[i]
		beforeIndex := i - 1 //下标

		for beforeIndex >= 0 && (*arr)[beforeIndex] > insertValue { // 前面的小于后面的
			(*arr)[beforeIndex+1] = (*arr)[beforeIndex] //数据后移
			beforeIndex--                               //索引前移
		}

		//插入
		(*arr)[beforeIndex+1] = insertValue
	}

}
